package String;

public class RepeatedSubstringPattern459 {
    public static void main(String[] args) {
        System.out.println(repeatedSubstringPattern("abcabcabcabc"));
    }
    public static boolean repeatedSubstringPattern(String s) {
        if (s == null) {
            return false;
        }
        int len = s.length();
        // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
//        s = " " + s;
//        char[] chars = s.toCharArray();
//        int[] next = new int[len + 1];
//
//        // 构造 next 数组过程，j从0开始(空格)，i从2开始
//        for (int i = 2, j = 0; i <= len; i++) {
//            // 匹配不成功，j回到前一位置 next 数组所对应的值
//            while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
//            // 匹配成功，j往后移
//            if (chars[i] == chars[j + 1]) j++;
//            // 更新 next 数组的值
//            next[i] = j;
//        }
        int[] next = kmpNext(s);


        // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
        if (next[len-1] > 0 && len % (len - next[len-1]) == 0) {
            return true;
        }
        return false;
    }

    static int[] kmpNext(String dest) {
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i = 1, j = 0; i < dest.length(); i++) {
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) { // 后缀结点j和前缀结点i不相同，
                                                                // 前缀结点根据next数组后移相应位置，
                                                                // 直到找到相同的结点
                j = next[j - 1];
            }
            if (dest.charAt(i) == dest.charAt(j)) {  // 后缀结点j和前缀结点i相同，前缀结点前移一位
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
